Peptide antigens recognized by human melanoma-reactive T cells can be incorporated in vaccines to induce immune responses against melanoma. Most work in this area has been limited to the use of single antigens, or few antigens, targeting only CD8+ T cells. These vaccines induce CD8+ T cell responses, but often of low magnitude, and objective tumor regressions have been uncommon. To improve vaccine strategies, it may help to increase the number of antigens targeted, to increase the magnitude of responses, to target both CD4 and CD8 T cells, and to increase persistence of the immune response through induction of memory. CD4 responses appear to be critical for immunologic memory, and for dendritic cell activation. Nonspecific stimulation of CD4 T cells may induce helper T cell responses at the site of vaccination;however, maintaining CD4 T-cell help at sites of tumor may require that they are stimulated more specifically toward melanoma antigens. Now that multiple peptide epitopes for helper T cells have been defined, it is feasible to assess their immunogenicity, and to determine whether they increase the magnitude and persistence of CD8 responses. The immunologic effects of vaccination with a multipeptide vaccine targeting CD4 and CD8 T cells will be evaluated in the clinical trial E1602. The peptide antigens used in this trial include (i) a cocktail of 12 melanoma peptides restricted by Class I MHC molecules HLA-A1, A2, or A3 (12MP), (ii) a cocktail of 6 melanoma helper peptides restricted by HLA-DR molecules (6MHP), and (iii) a modified tetanus peptide, restricted by HLA-DR molecules (tet). Patients with advanced melanoma will be randomized to one of 4 vaccine strategies: (a) 12MP only, (b) 12MP + tet, (c) 12MP + 6 MHP, and (d) 6MHP only. The current application is for immunologic studies of T cell responses to these multipeptide vaccines, as well as for shipping costs and for costs of vaccine adjuvant. Blood and tissues for immune monitoring will be shipped, prepared, and cryopreserved centrally at the Immune Monitoring and Cellular Products Laboratory (IMCPL) at the University of Pittsburgh, which is the Core Laboratory for the Eastern Cooperative Oncology Group (ECOG) and has experience and certification in cryopreservation. The cellular immune monitoring assays will be performed by the Human Immune Therapy Center Laboratory at the University of Virginia. Cytokine assays will be done at the Pittsburgh IMCPL. Specific aims are: 1) To estimate whether addition of helper peptides to a vaccine containing multiple Class I MHC-restricted peptides augments T-cell responses to the Class I restricted peptides;2) To characterize the phenotype of vaccine-induced CD8+ T cells for effector and memory phenotypes;3) To determine the helper T cell response to tetanus peptide and to each of 6 melanoma helper peptides, restricted by multiple HLA-DR molecules;4} To obtain preliminary data on whether booster vaccination every three months may maintain immune responses to a peptide vaccine, in patients with stage IV melanoma;and 5) To obtain preliminary data on whether cellular immune responses to a 12-peptide vaccine may correlate with clinical outcome, among the four arms of this study.